/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2022并保留所有权利。
 * Copyright 2022, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */

package com.azdebugit.suanfa.test.teshuawei.test.快慢指针;

/**
 * Title：NC53-删除链表倒数第n个值,并返回头结点
 * Description： 要求O(n)
 * @author WZQ
 * @version 1.0.0
 * @date 2021/2/27
 */
public class NC53 {

    /**
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        if(head == null){
            return head;
        }

        // 双指针，快慢指针
        // 采用两个指针，对前指针，使其先走出N步，随后两个指针同时前进，
        // 当前指针到达链表尾部时，后指针到达倒数第N个节点的位置。
        ListNode slow = head;
        ListNode fast = head;

        // 先走n步
        for(int i = 0; i <n; i++){
            fast = fast.next;
        }

        // //如果n的值等于链表的长度,直接返回去掉头结点的链表
        // 删除的节点是头节点的情况
        if(fast == null) {
            return head.next;
        }

        // 快指针走到尾部，慢指针位置删除
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return head;
    }
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
